﻿#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>

template <typename T>
class BST {
private:
    // 二叉树节点结构
    struct Node {
        T data;         // 节点存储的数据
        Node* left;     // 左子节点指针
        Node* right;    // 右子节点指针

        Node(T value) : data(value), left(nullptr), right(nullptr) {}
    };

    Node* root;  // 根节点指针

    // 递归插入辅助函数

    /*
	先创建根节点创建对象插入，在左边和右边节点插入，在插入时判断值小于节点值插入左边，大于节点值插入右边，等于不插入
    
    */
    Node* insert(Node* node, T value) {
        if (node == nullptr) {
            return new Node(value);  // 创建新节点
        }

        if (value < node->data) {
            node->left = insert(node->left, value);  // 插入到左子树
        }
        else if (value > node->data) {
            node->right = insert(node->right, value); // 插入到右子树
        }

        return node;  // 返回当前节点
    }

    // 查找最小节点
    Node* findMin(Node* node) {
        while (node->left != nullptr) {
            node = node->left;  // 一直向左查找
        }
        return node;
    }

    // 递归删除辅助函数
    Node* remove(Node* node, T value) {
        if (node == nullptr) return nullptr;  // 节点不存在

        if (value < node->data) {
            node->left = remove(node->left, value);  // 在左子树中删除
        }
        else if (value > node->data) {
            node->right = remove(node->right, value); // 在右子树中删除
        }
        else {
            // 找到要删除的节点
            if (node->left == nullptr) {  // 只有右子节点
                Node* temp = node->right;
                delete node;
                return temp;
            }
            else if (node->right == nullptr) {  // 只有左子节点
                Node* temp = node->left;
                delete node;
                return temp;
            }

            // 有两个子节点的情况：用右子树的最小值替换当前节点
            Node* temp = findMin(node->right);
            node->data = temp->data;  // 复制数据
            node->right = remove(node->right, temp->data);  // 删除右子树中的最小节点
        }

        return node;
    }

    // 递归搜索辅助函数
    bool search(Node* node, T value) const {
        if (node == nullptr) return false;  // 未找到

        if (value == node->data) return true;  // 找到目标
        else if (value < node->data) return search(node->left, value);  // 在左子树中搜索
        else return search(node->right, value);  // 在右子树中搜索
    }

    // 中序遍历辅助函数（左-根-右）
    void inOrder(Node* node) const {
        if (node == nullptr) return;
        inOrder(node->left);
        std::cout << node->data << " ";
        inOrder(node->right);
    }

    // 前序遍历辅助函数（根-左-右）
    void preOrder(Node* node) const {
        if (node == nullptr) return;
        std::cout << node->data << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    // 后序遍历辅助函数（左-右-根）
    void postOrder(Node* node) const {
        if (node == nullptr) return;
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->data << " ";
    }

    // 计算树的高度
    int height(Node* node) const {
        if (node == nullptr) return -1;  // 空树高度为-1
        return 1 + std::max(height(node->left), height(node->right));
    }

    // 计算树的大小（节点数量）
    int size(Node* node) const {
        if (node == nullptr) return 0;  // 空子树大小为0
        return 1 + size(node->left) + size(node->right);
    }

    // 清空树的辅助函数
    void clear(Node* node) {
        if (node == nullptr) return;
        clear(node->left);   // 清空左子树
        clear(node->right);  // 清空右子树
        delete node;         // 删除当前节点
    }

    // 复制树的辅助函数（深拷贝）
    Node* copy(Node* node) const {
        if (node == nullptr) return nullptr;

        Node* newNode = new Node(node->data);  // 创建新节点
        newNode->left = copy(node->left);      // 复制左子树
        newNode->right = copy(node->right);    // 复制右子树

        return newNode;
    }

public:
    // 构造函数和析构函数
    BST() : root(nullptr) {}  // 默认构造函数

    BST(const BST& other) {   // 拷贝构造函数
        root = copy(other.root);
    }

    BST& operator=(const BST& other) {  // 赋值运算符重载
        if (this != &other) {
            clear();
            root = copy(other.root);
        }
        return *this;
    }

    ~BST() {  // 析构函数
        clear();
    }

    // 公共接口

    // 插入元素
    void insert(T value) {
        root = insert(root, value);
    }

    // 删除元素
    void remove(T value) {
        root = remove(root, value);
    }

    // 搜索元素
    bool search(T value) const {
        return search(root, value);
    }

    // 检查树是否为空
    bool isEmpty() const {
        return root == nullptr;
    }

    // 获取树的高度
    int height() const {
        return height(root);
    }

    // 获取树的节点数量
    int size() const {
        return size(root);
    }

    // 清空树
    void clear() {
        clear(root);
        root = nullptr;
    }

    // 遍历方法

    // 中序遍历
    void inOrder() const {
        inOrder(root);
        std::cout << std::endl;
    }

    // 前序遍历
    void preOrder() const {
        preOrder(root);
        std::cout << std::endl;
    }

    // 后序遍历
    void postOrder() const {
        postOrder(root);
        std::cout << std::endl;
    }

    // 层次遍历（广度优先）
    void levelOrder() const {
        if (root == nullptr) return;

        std::queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* current = q.front();
            q.pop();
            std::cout << current->data << " ";

            if (current->left != nullptr) q.push(current->left);
            if (current->right != nullptr) q.push(current->right);
        }
        std::cout << std::endl;
    }

    // 迭代方式的中序遍历
    void inOrderIterative() const {
        std::stack<Node*> s;
        Node* current = root;

        while (current != nullptr || !s.empty()) {
            while (current != nullptr) {
                s.push(current);
                current = current->left;  // 一直向左
            }

            current = s.top();
            s.pop();
            std::cout << current->data << " ";  // 访问节点
            current = current->right;  // 转向右子树
        }
        std::cout << std::endl;
    }

    // 获取最小值
    T getMin() const {
        if (root == nullptr) throw std::runtime_error("树为空");

        Node* current = root;
        while (current->left != nullptr) {
            current = current->left;  // 一直向左查找
        }
        return current->data;
    }

    // 获取最大值
    T getMax() const {
        if (root == nullptr) throw std::runtime_error("树为空");

        Node* current = root;
        while (current->right != nullptr) {
            current = current->right;  // 一直向右查找
        }
        return current->data;
    }

    // 检查是否为合法的二叉搜索树
    bool isBST() const {
        return isBST(root, nullptr, nullptr);
    }

private:
    // 检查BST合法性的辅助函数
    bool isBST(Node* node, Node* minNode, Node* maxNode) const {
        if (node == nullptr) return true;

        // 检查当前节点值是否在允许范围内
        if ((minNode != nullptr && node->data <= minNode->data) ||
            (maxNode != nullptr && node->data >= maxNode->data)) {
            return false;
        }

        // 递归检查左右子树
        return isBST(node->left, minNode, node) &&
            isBST(node->right, node, maxNode);
    }
}; int main() {
    BST<int> tree;

    // 插入元素
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);
   // tree.insert(50);

    // 遍历演示
    std::cout << "中序遍历: ";
    tree.inOrder();

    std::cout << "前序遍历: ";
    tree.preOrder();

    std::cout << "后序遍历: ";
    tree.postOrder();

    std::cout << "层次遍历: ";
    tree.levelOrder();

    // 搜索演示
    std::cout << "搜索40: " << (tree.search(40) ? "找到" : "未找到") << std::endl;
    std::cout << "搜索100: " << (tree.search(100) ? "找到" : "未找到") << std::endl;

    // 获取极值
    std::cout << "最小值: " << tree.getMin() << std::endl;
    std::cout << "最大值: " << tree.getMax() << std::endl;

    // 树信息
    std::cout << "树高度: " << tree.height() << std::endl;
    std::cout << "节点数量: " << tree.size() << std::endl;

    // 删除演示
    tree.remove(30);
    std::cout << "删除30后中序遍历: ";
    tree.inOrder();

    return 0;
}